package ch04.shortest_path;

import static java.lang.Math.min;

public class Flord {

    private static int n;
    private static double[][] dis;
    public static final double INF = Double.MAX_VALUE;

    private static void init() {
        n = 10;
        dis = new double[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = INF;
            }
        }


    }

    public static void flord() {
        //提前将邻接矩阵存在dis数组里，其他不连通的地方初始化成无穷大
        for (int k = 1; k <= n; ++k)//枚举中间点
            for (int i = 1; i <= n; ++i)//枚举起点
                if (i != k)//节省时间，如果一样就不往下走
                    for (int j = 1; j <= n; ++j)//枚举终点
                        if (i != j && j != k)//继续判断，如果有一样的就不往下走
                            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);//状态转移方程，也就是所谓的松弛操作
    }


}
